While images have always been incorporated into documents as an efficient way to convey information to readers, the exploding use of personal computers coupled with computerization of an increasingly diverse array of image-related applications has substantially increased the need to manipulate images in digital form. These manipulations frequently include, inter alia, scaling, rotating and halftoning.
Beginning several years ago and continuing with increasing use to the present, documentary images are often processed through a computer using a so-called page description language. Such a language allows a user to define objects, such as an image, that are to appear on a printed page and allows the objects to be processed in a desired fashion and then accurately positioned with respect to each other in order to properly form an entire page. To provide maximum flexibility to a user in processing a digital image, a page description language would need to support, with floating point precision, both arbitrary uniform and anamorphic image scaling within finite bounds, image rotation by an arbitrary angle, and halftoning with arbitrary screen angles and screen rulings. In order to assure that a documentary image properly "mates up" with other objects on a page, these image processing functions must be very accurately implemented, otherwise artifacts or other errors will appear on the page, when printed.
While several different page description languages are currently in use, serious limitations exist in the two basic approaches through which these languages have been traditionally implemented to perform, inter alia, image scaling and rotation.
Specifically, one basic approach widely used in the art relies on storing an entire image within a random access frame memory and then operating on the individual bits of the image situated therein. This approach, hereinafter referred to as the "full frame memory" approach, may involve sequentially reading the image, bit-by-bit, using suitable incrementing memory addresses to generate appropriately rotated image data to yield a rotated image. As known in the art, scaling may involve, for example, adding or deleting data to or from selected pixel locations in the memory in order to change the scale of the image, as desired. This overall approach requires a sufficiently large frame memory that also provides relatively fast read-write random access. Unfortunately, for an 8-by-10 inch (approximately 20-by-25 cm) continuous tone image printed at a resolution of 300 dots/inch (approximately 118 dots/cm) which is readily obtainable with currently available output writers, e.g. laser printers, the frame memory would require approximately 7 MBytes. A memory of this size, particularly when fabricated from currently available high speed random access memory (RAM) circuits, tends to be very expensive. The inordinate cost of such a frame memory generally precludes its use in a low cost printer. Furthermore, even with such a large, fast memory, image scaling and rotation are often performed through a software based process executing in a microprocessor and, as such, for an entire image, tends to be relatively slow.
In view of the practical memory limitation, the art has, for some time, also taught that scaling and rotation could alternately be preformed on a "tile-based" approach. Here, an image is first partitioned into small uniform regions called "tiles", each of which is then separately and appropriately processed. Typically, a tile is significantly smaller than the entire image. Once a tile is processed to yield an output tile, that output tile is then written into a spatially corresponding region in an output buffer, and so on for all such tiles until an entire image has been formed of output tiles.
Given these two approaches, tiling offers several distinct advantages. First, by drastically reducing the size of a tile down from that of the entire image, memory requirements for a high speed frame memory are substantially reduced from, for example, 7 MBytes for storing an entire image to perhaps 10 KBytes for storing a single tile currently being processed. This, in turn, obviates the need for a large full size high speed frame memory thereby simplifying and significantly reducing the cost of the system memory. While an image size output buffer would still be required, this buffer would not need to function as a high speed random access memory and thus can be fabricated from relatively slow and inexpensive memory circuits. Furthermore, by processing a single tile at a time, data transfers involving the frame memory are reduced to the data required just for a particular tile rather than that of the entire image as in the "full frame memory" approach. Consequently, the operations required to perform these memory transfers are greatly simplified and, as such, merely become an incidental portion of the overall tile-based processing. Moreover, by processing only a relatively small amount of data at any one time, specialized hardware circuits can be easily fabricated to rapidly process an entire tile and thereby accelerate the rate at which the entire image can be rotated and/or scaled over that associated with the "full frame memory" approach. Lastly, tile-based implementations tend to readily lend themselves to pipelined and parallel processing through which appropriate tile processing hardware is duplicated and operated on a parallel and time-staggered basis to permit several tiles to be collectively processed at once. This, in turn, further accelerates the overall process of image scaling and/or rotation. Advantageously, such implementations can easily be upwardly scaled in size, consistent with cost-performance tradeoffs, to achieve a desired throughput level.
Unfortunately, for all the advantages exhibited by tile-based scaling and rotation, a tile-based approach, particularly when used for halftoning, necessitates that each output tile must be very accurately placed in the output buffer else visible flaws will occur in the image. Specifically, we have empirically observed that for a halftoned image with a 50% tint factor, a one pixel offset in the halftoning pattern between adjacent tiles causes visible artifacts to appear in the image. These artifacts take the form of "zig-zag" lines that occur along the tile boundaries all throughout the image. As a result, if an image is to be subsequently halftoned, then a screener operating on those tiles is required to obtain each tile from the output buffer, screen that tile and place that tile back into the output buffer with a one-bit accuracy. Achieving and maintaining such a high accuracy throughout the entire halftoning process for an image has proven to be extremely difficult to attain in practice.
At first blush, one might think that this accuracy could be relaxed and the "zig-zag" pattern eliminated by appropriately smoothing the boundaries of the halftoned tiles. Specifically, such smoothing, implemented through low pass spatial filtering, would reduce the visual impact of rounding errors and resulting tile mis-alignment that would otherwise result when floating point address values are truncated into real integer addresses which, in turn, are used to address an output buffer into which the halftoned tiles are re-assembled. Through suitable experimental observations, we have noticed that, while such filtering does reduce visible tile mis-alignment, unfortunately this filtering breaks up and thereby corrupts the underlying halftone dot structure in the image. Therefore, we believe that tile boundary filtering does not appear to offer a viable solution and one-bit accuracies do need to be maintained in tile-based image processing.
Furthermore, apart from tiling, commercially available screeners are expensive, require inordinate amounts of memory and often do not possess the capability of performing image scaling and/or rotation.
In addition, image scaling and rotation are frequently carried out in currently available image processing apparatus as "front-end" operations, i.e. in circuitry situated near an image scanner in a chain of image processing circuits; while screening is carried out as a "back-end" operation, i.e. in circuitry associated with an output writer. Either operation generally has little, and oftentimes no knowledge, of the other with, as a result, artifacts and other adverse consequences frequently manifesting themselves in the image. Since page description languages perform post-processing, i.e. these languages process an image as they "find it", these languages provide no opportunity to optimize an image for operations that have previously been performed on it, such as "front-end" scaling or rotation. As such, the specific implementation of these languages, as currently used, does not eliminate adverse affects, such as Moire patterns and aliasing, that might result from interaction between various characteristics of these "front-end" operations, such as for example sampling frequencies and pixel placement, with similar corresponding characteristics associated with the halftoning process and the output writer.
Moreover, commercially available screeners also tend to be inordinately slow. Accordingly, if such a screener were to be used in implementing a page description language, then the resulting throughput provided thereby would be substantially less than the speed, in pages/minute (ppm), of currently available output writers, such as upwards of 70 ppm, and would thus pose a serious bottleneck. Inordinately slow speeds would tend to frustrate users, who, in turn, would rather shy away from and not incorporate images into documents than wait the needed time for each of these images to be processed and printed.
In spite of the basic drawbacks noted above, the advantages inherent in a tiled-based approach, particularly those flowing from the reduction in size and cost of the frame buffer, strongly support its use.
Therefore, a need exists in the art for a tile-based technique that can very accurately and inexpensively implement image rotation, scaling and halftoning in a post-processing environment. Furthermore, a specific need exists to implement tile-based scaling, rotating and halftoning in a manner that can significantly accelerate the throughput of a page description language to approach that of currently available output writers. Advantageously, the incorporation of such a technique in an output writer will significantly hasten the use of documentary images.